package org.example.myleet.rosalind.ling;

import java.io.*;
import java.util.*;

/**
 * 题目地址：https://rosalind.info/problems/ling/
 */
public class Solution {

    /**
     * @return 判断从字符串s的s1和s2位置开始，l长度的子串是否相同
     */
    private static boolean isIdentical(String s, int s1, int s2, int l) {
        if (s1 + l > s.length() || s2 + l > s.length()) {
            return false;
        }
        for (int i = 0; i < l; ++i) {
            if (s.charAt(s1 + i) != s.charAt(s2 + i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * @return 通过Rabin Karp算法筛选一个字符串中不同长度的子串是否真子串
     */
    private static long countDistinctSubstrings(String s) {
        int n = s.length();
        // store prime to reduce overflow
        long mod = 9007199254740881L;
        // substrings count
        long substringCnt = 0;
        for (int k = 1; k <= n; k++) {
            // to store hash values by Rabin Karp algorithm
            Map<Long, Integer> hvMapPoint = new HashMap<>();
            //l -> substring length, from 1 to n
            long hashVal = 0;
            long h = 1;
            // Number of input alphabets
            int D = 4;
            //初始化hash值
            for (int i = 0; i < k; ++i) {
                hashVal = (hashVal + s.charAt(i)) * D % mod;
                h = (h * D) % mod;
            }
            hvMapPoint.put(hashVal, 0);
            substringCnt++;
            for (int i = 1; i + k <= n; ++i) {
                //滚动计算hashVal，hashVal+mod是为了防止减s.charAt(i-1)*h的值变成负数
                //由于这里只有加法、减法和乘法，因此准确计算一个超大数字最后的十几位数字，这是取余操作的用法
                hashVal = (hashVal + mod - s.charAt(i - 1) * h + s.charAt(i + k - 1)) * D % mod;
                Integer p = hvMapPoint.get(hashVal);
                if (null == p) {
                    //不存在这个子串的hashVal，代表这个子串是真子串
                    hvMapPoint.put(hashVal, i);
                    substringCnt++;
                } else {
                    //遇到hashVal相同的情况（哈希碰撞），需要整个子串比对一次确认是不一样的才可以算作是一个新的真子串
                    boolean identical = isIdentical(s, p, i, k);
                    if (!identical) {
                        substringCnt++;
                    }
                }
            }
        }
        return substringCnt;
    }

    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
//        String path = solution.getClass().getResource("").getPath() + "rosalind_ling.txt";
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        String sequence = br.readLine().trim();
        int n = sequence.length();
//        System.out.println(dna);
        //计算substring的数量，方法是，从1~n长度，逐个长度对字符串滑窗取出子字符串，统计子字符串的种类数
        long distinctSubstringCnt = 0;
        //下面注释部分是暴力的方式进行滑窗并检查真子串的方式，对于测试数据100kbp的文件，30秒只能跑出k
//        for (int l = 1; l <= n; ++l) {
//            Map<String, Integer> substringPrefixMapHashCode = new HashMap<>();
//            StringBuilder sb = new StringBuilder();
//            for (int i = 0; i < l; ++i) {
//                sb.append(sequence.charAt(i));
//            }
//            String prefix = l < 10 ? sb.toString() : sb.substring(0, 10);
//            substringPrefixMapHashCode.put(prefix, sb.hashCode());
//            ++substringCnt;
//            for (int i = 1; i + l <= n; ++i) {
//                sb.deleteCharAt(0);
//                sb.append(sequence.charAt(i + l - 1));
//                prefix = l < 10 ? sb.toString() : sb.substring(0, 10);
//                if (substringPrefixMapHashCode.containsKey(prefix)) {
//                    if (substringPrefixMapHashCode.get(prefix) != sb.hashCode()) {
//                        ++substringCnt;
//                    }
//                } else {
//                    substringPrefixMapHashCode.put(prefix, sb.hashCode());
//                    ++substringCnt;
//                }
//            }
//        }
//        substringCnt = countDistinctSubstrings(sequence);

        // store prime to reduce overflow
        long mod = 9007199254740881L;

        //计算m(a,k,n)的结果，k为子串的长度，设字符集合的大小为A，则m(a,k,n) = min(n+1-k, A^k)，即可能为A^k，但最多不超过n+1-k种可能
        boolean finish = false;
        long m = 0;
        int possibleSubstringCnt = 1;
        for (int k = 1; k <= n; ++k) {
            if (possibleSubstringCnt < n) {
                possibleSubstringCnt = possibleSubstringCnt * 4;
            }
            int m_ = Math.min(n + 1 - k, possibleSubstringCnt);
            m += m_;
            //下面使用了整合的Rabin Karp算法，并进行了取巧操作。
            if (!finish) {
                //Rabin Karp
                int s_ = 0;
                // to store hash values by Rabin Karp algorithm
                Map<Long, Integer> hvMapPoint = new HashMap<>();
                //l -> substring length, from 1 to n
                long hashVal = 0;
                long h = 1;
                // Number of input alphabets
                int D = 4;
                for (int i = 0; i < k; ++i) {
                    hashVal = (hashVal + sequence.charAt(i)) * D % mod;
                    h = (h * D) % mod;
                }
                hvMapPoint.put(hashVal, 0);
                s_++;
                for (int i = 1; i + k <= n; ++i) {
                    hashVal = (hashVal + mod - sequence.charAt(i - 1) * h + sequence.charAt(i + k - 1)) * D % mod;
                    Integer p = hvMapPoint.get(hashVal);
                    if (null == p) {
                        hvMapPoint.put(hashVal, i);
                        s_++;
                    //取巧操作1，为了加快速度，只按hashVal比对结果为准
    //                } else {
    //                    boolean identical = isIdentical(s, p, i, l);
    //                    if (!identical) {
    //                        subStringCnt++;
    //                    }
                    }
                    if (s_ >= m_) break;
                }
                distinctSubstringCnt += s_;
                if (k > 100 && s_ == m_) {
                    //取巧操作2，经过调试运行总结规律后，我发现其实到后面某个k值之后，最大可能子串数和真子串数是相同的，那就不再比对了，直接按最大可能子串数座位真子串数
                    //猜想原因是越到后面其实最大可能子串数越来越少，而其前缀其实是基于更小的k值产生的子串（其前缀是k值更小的子串的子集），而这些子串一旦都全是真子串的情况下，则其子集也一定全是真子串
                    finish = true;
                }
            } else {
                //取巧操作2
                distinctSubstringCnt += m_;
            }
        }
        //lc(s) = sub(s) / m(a,k,n)
        double lc = (double) distinctSubstringCnt / m;
        System.out.println(lc);
    }
}
